The present invention relates to the simulation and visual representation of interactive 3-D characters by digital computers.
A new generation of personal computers (PCs) and set-top boxes is now coming onto the market. These are capable of computing real-time 3D graphics such as character animation. However, interfaces for controlling these animated characters typically only allow only the sequential playback of stored animations, or for xe2x80x9cpuppeteeringxe2x80x9d (direct user manipulation) through joystick, mouse, and other user interface devices. In real-world experience, human (and even animal) characters respond to language-based commands and questions, exhibit visible manifestations of mental and emotional state, direct attention to appropriate objects and events, and respond with voice, gesture, body language, and demonstration. This xe2x80x9canimation from natural languagexe2x80x9d is necessary to provide natural user interfaces to characters that appear to have higher-order intelligence.
In order to fully address the novelty and advantages of the present invention, it is helpful to first survey the current art of both the computer modeling and the computer animation of characters. In this context, modeling refers to the creating the geometry and appearance of the character. Animation refers to the methods of controlling the motion of the computer-generated character, and synchronizing this motion with sound and other elements of the simulated environment.
The most common method for modeling 3-D characters intended for real-time computer animation is described by the Specification for a Standard Humanoid (version 1.1) of the Web3D Consortium""s Humanoid Animation Working Group. As described in that document:
xe2x80x9cThe human body consists of a number of segments (such as the forearm, hand and foot) which are connected to each other by joints (such as the elbow, wrist and ankle). In order for an application to animate a humanoid, it needs to obtain access to the joints and alter the joint angles. The application may also need to retrieve information about such things as joint limits and segment masses.
xe2x80x9cEach segment of the body will typically be defined by a mesh of polygons, and an application may need to alter the locations of the vertices in that mesh. The application may also need to obtain information about which vertices should be treated as a group for the purpose of deformation.
xe2x80x9cA VRML Humanoid file contains a set of Joint nodes that are arranged to form a hierarchy. Each Joint node can contain other Joint nodes, and may also contain a Segment node which describes the body part associated with that joint.xe2x80x9d
The most common method for computer animation of 3-D characters is exemplified by Stern in U.S. Pat. No. 4,600,919, titled Three Dimensional Animation. In this method, the motion of the limbs of a character are represented by a series of key frames, with each key frame defining the position and orientation of each segment of the character""s body. A computer system then generates a series of in-between frames by interpolating the position and orientation of each vector for each displayed video frame. This approach has the limitation that, unless the original key frames are properly selected, one body part may collide with, or intersect with, another body part as the trajectories of the body segment vectors are interpolated from one in-between frame to the next.
Other developers in the field of real-time character animation have identified methods for sequencing, overlapping, and blending basic animations, wherein each of the component animations can be defined by key frames. Dow et al. (ref. U.S. Pat. No. 5,877,778), for example, teach a method for smoothing from one animation to a following animation. However, again, this method does not include a means for resolving body segment collisions. Nor does it include a means for translating a series of natural language commands into a natural motion representation. Koga et al. (1994) have developed a method for simulating the motion of the arm when grasping and moving objects. However, this method does not identify and avoid potential collisions of the arm with the torso. Nor does it include a method for simulating finger motion.
Badler (1999) has developed a Parallel Transition Network (Pat-Net) approach to animating multiple, potentially parallel actions from natural language. However, each Pat-Net implementation must be individually programmed, and there is no automated methodology for body part collision avoidance.
Accordingly, several objects and advantages of the present invention are:
(a) To simplify the process of character animation, such that complex and realistic, interactive animations may be developed and commanded in a high-level language by individuals not trained in the art of animation.
(b) To provide a method using very low computational requirements for identifying and avoiding impending intersections of body part trajectories.
(c) To reduce data bandwidth requirements, relative to existing animation techniques, by pre-storing key-framed and algorithmically defined animations that may be composited into complex animation in real time.
(d) To provide a method for simulating autonomous behaviors, including blinking, direction of gaze, and fidgeting.
This invention is a method and a system to automatically create complex, compound character animations from stored and/or synthesized basic action animations. Each compound animation is defined by command sequences that command actions to be performed in sequence or in parallel. These actions may include facial expression, orientation of gaze, and speech with lip-synching, as well as body movement. This invention provides methods and systems to automatically arbitrate, sequence, and synchronize various commanded actions, while identifying and avoiding actions and transitions between actions that are physically impossible or improbable, such as body part interferences, unachievable rates of motion, and unnatural stretching or separation of the skin. In this manner, the invention enables the real-time simulation on low-cost client computers, of complex and realistic character actions that are controlled by simple high-level commands that are received at low bandwidth over a network, or are computed locally. The invention includes methods and systems for defining transition behavior based on easily edited data tables. It is also highly optimized for real-time performance. Specific applications of this invention include: 1) supplementing character vocal communication with appropriate gesturing and demonstration, 2) real-time translation of spoken or written language to sign language, and 3) interactive educational and entertainment software in which a character responds intelligently to user actions.